package com.wangzemin.leetcode.num138;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Map<Node, Node> copyMap = new HashMap<Node, Node>();
        Node copyHead = new Node(head.val);
        copyMap.put(head, copyHead);
        Node originHead = head;

        Node curCopy = copyHead;
        while (head.next != null) {
            Node nextNode = new Node(head.next.val);
            copyMap.put(head.next, nextNode);
            curCopy.next = nextNode;
            curCopy = curCopy.next;
            head = head.next;
        }

        head = originHead;
        curCopy = copyHead;
        while (curCopy != null && head!=null) {
            Node originRandom = head.random;
            if (originRandom!=null){
                curCopy.random = copyMap.get(originRandom);
            }
            curCopy = curCopy.next;
            head = head.next;
        }
        return copyHead;
    }
}